1809F - Traveling in Berland - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ve vector
#define se second
#define fi first
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll a[200000], b[200000], pref[400000], last[400000], p[400000], r[400000];


void solve(){
    ll n, k;
    cin >> n >> k;
    bool no1 = 1;

    for(int i = 0; i < n; i++)cin >> a[i];
    for(int i = 0; i < n; i++){
        cin >> b[i];
        if(b[i] == 1)no1 = 0;
    }


    for(int i = 0; i < 2*n; i++){
        r[i] = i%n;
    }

    ll sum = 0;
    for(int i = 0; i < n; i++)sum += a[i];

    ll w = 0;
    ll cost = 0;

    int id = 2*n-1;
    ll path = 0;
    for(int it = 2*n-1; it>=0; it--){
        if(it != 2*n-1){
            path += a[r[it]];
        }

        p[it] = path;
        last[it] = id;

        if(b[r[it]] == 1){
            id = it;
        }
    }

    for(int it = 0; it < 2*n; it++){
        pref[it] = cost - w;
        if(b[r[it]] == 1){
            if(p[it]-p[last[it]] > k){
                cost += k-w;
                w = k;
            }
            else if(p[it]-p[last[it]] > w){
                ll need = p[it]-p[last[it]];
                cost += need;
                w += need;
            }
        }
        else{
            if(w < a[r[it]]){
                ll need = a[r[it]] - w;
                cost += 2*need;
                w += need;
            }
        }
        w -= a[r[it]];
    }

    for(int v = 0; v < n; v++){
        ll ans;
        if(no1){
            ans = 2*sum;
        }
        else if(b[v] == 1){
            ans = pref[v+n] - pref[v];
        }
        else{
            ans = pref[v+n] - pref[last[v]] + 2*(p[v] - p[last[v]]);
        }
        cout << ans << ' ';
    }
    cout << '\n';
}



int main()
{
//    ifstream cin("input.txt");
//    ofstream cout("output.txt");
    ios_base::sync_with_stdio(0);cin.tie(0);

    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}